<?php
/*
剑指 Offer 34. 二叉树中和为某一值的路径
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：
输入：root = [1,2], targetSum = 0
输出：[]


提示：
树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000



难度：中等

https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/


*/

require_once '../class/TreeNode.class.php';
$arr1 = [1,2];$targetSum = 1;
$arr1 = [5,4,8,11,null,13,4,7,2,null,null,5,1];$targetSum = 22;
$root1 = generateTreeByArray($arr1);
$obj = new Code_Offer34();
$res = $obj->main($root1, $targetSum);
var_dump($res);

class Code_Offer34
{
    public $res = [];
    public function main($root, $target)
    {
        if (!$root) {
            return $this->res;
        }
        $this->_dfs($root, $target, []);

        return $this->res;
    }

    protected function _dfs($node, $target, $arr)
    {
        if ($node == null) {
            return;
        }
        if ($node->val == $target && $node->left == null && $node->right == null) {
            $arr[] = $node->val;
            $this->res[] = $arr;
            return;
        }
        $arr[] = $node->val;
        $this->_dfs($node->left, $target - $node->val, $arr);
        $this->_dfs($node->right, $target - $node->val, $arr);

    }
}